ML-Cheat-Sheet

Basic Rules of Differentiation

Basic Rules

• Constant Rule: $\frac{d}{dx}C=0$

• Power Rule: $\frac{d}{dx}{x}^n=n{x}^{n-1}$

• Linear Combination: $\frac{d}{dx}[af(x)+bg(x)]=a{f}^{\prime }(x)+b{g}^{\prime }(x)$

• Product Rule: $\frac{d}{dx}[f(x)g(x)]=f^{\prime }(x)g(x)+f(x)g^{\prime }(x)$

• Quotient Rule: $\frac{d}{dx}\left[\frac{f(x)}{g(x)}\right]=\frac{f^{\prime }(x)g(x)-f(x)g^{\prime }(x)}{[g(x){]}^2}$

• Chain Rule: $\frac{d}{dx}f(g(x))=f^{\prime }(g(x))g^{\prime }(x)$

• Exponential:$\frac{d}{dx}{e}^x=e^x$ | |$\frac{d}{dx}{a}^x=a^x\ln (a)$

• Logarithmic $\frac{d}{dx}\ln (x)=\frac{1}{x}$ || $\frac{d}{dx}{\log }_a(x)=\frac{1}{x\ln (a)}$

Linear Regression

1. Hypothesis

$h_{\theta }(x)={\theta }^{T}x={\theta }_0+{\theta }_1{x}_1+\cdots +{\theta }_n{x}_n$

2. Cost Function

Mean Squared Error (MSE): $J(\theta )=\frac{1}{2m}\sum _{i=1}^m{(h_{\theta }(x^{(i)})-y^{(i)})}^2$

3. Optimization

• Gradient Descent: ${\theta }_j:={\theta }_j-\alpha \frac{1}{m}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)})x_j^{(i)}$
• Normal Equation: $\theta ={\left(X^{T}X\right)}^{-1}{X}^{T}y$

---

Logistic Regression

1. Hypothesis

$h_{\theta }(x)=\frac{1}{1+e^{-{\theta }^{T}x}}$

• Prediction Rule:
  • Predict $y=1$ if $h_{\theta }(x)\ge 0.5$, otherwise $y=0$.

2. Cost Function

Log Loss: $J(\theta )=\frac{1}{m}\sum _{i=1}^m[-y^{(i)}\log (h_{\theta }(x^{(i)}))-(1-y^{(i)})\log (1-h_{\theta }(x^{(i)}))]$

3. Optimization

• Gradient Descent: ${\theta }_j:={\theta }_j-\alpha \frac{1}{m}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)})x_j^{(i)}$

4. Sigmoid Properties

• Output: $g(z)\in [0,1]$
• Derivative: $g^{\prime }(z)=g(z)(1-g(z))$

---

Ridge Regression

Loss Function

Adds $L2$ regularization to prevent overfitting: $J(\theta )=\frac{1}{2m}\sum _{i=1}^m{(h_{\theta }(x^{(i)})-y^{(i)})}^2+\lambda \sum _{j=1}^n{\theta }_j^2$

• $\lambda$: Regularization parameter. Higher values shrink ${\theta }_j$.

Optimization

• Closed-form Solution: $\theta ={(X^{T}X+\lambda I)}^{-1}{X}^{T}y$
• Gradient Descent: ${\theta }_j:={\theta }_j-\alpha (\frac{1}{m}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)})x_j^{(i)}+2\lambda {\theta }_j)$

Bayesian Classification

Dataset

• $T=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\}$
• $x_i=(x^1,\dots ,x^n)$, $y_i\in \{c_1,\dots ,c_K\}$

Posterior Probability

The probability of class $c_k$ given input $x$: $P(y=c_k\mid x)\propto P(y=c_k)P(x\mid y=c_k)$

If features are conditionally independent: $P(y=c_k\mid x)\propto P(y=c_k)\prod _{j}P(x^j\mid y=c_k)$

SVM

Hard SVMHyperplane: $H=\{w|w^{T}x+b=0\}$Constraint: $y_i(w^T{x}_i+b)\ge 1$ $\mathrm{\forall }i$Goal: $min\frac{1}{2}||w|{|}^2$ s.t. $y_i(w^t{x}_i+b)\ge 1$Lagrangian:$L(w,b,\alpha )=\frac{1}{2}||w|{|}^2-\sum _i{\alpha }_i(y_i(w^T{x}_i+b)-1),{\alpha }_i\ge 0$Partial derivative: $\frac{\partial L}{\partial w}=w-\sum _i{\alpha }_i{y}_i{x}_i=0$ $\frac{\partial L}{\partial b}=-\sum _i{\alpha }_i{y}_i=0$Solution: $||w|{|}^2=(\sum _i{\alpha }_i{y}_i{x}_i{)}^T(\sum _i{\alpha }_i{y}_i{x}_i)=\sum _i\sum _j{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$Lagrangian becomes: $L=\sum _i{\alpha }_i-\frac{1}{2}\sum _i\sum _j{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$s.t. $\sum _i{\alpha }_i{y}_i=0$ and ${\alpha }_i\ge 0\mathrm{\forall }i$Weight vector: $w^{\ast }=\sum _i{\alpha }_i{y}_i{x}_i$Bias: $b^{\ast }=y_i-\sum _i{\alpha }_i{y}_i{x}_i^T{x}_j$

Soft SVMHyperplane: $H=\{w|w^{T}x+b=0\}$Constraint: $y_i(w^T{x}_i+b)\ge 1-{\xi }_i,{\xi }_i\ge 0,\mathrm{\forall }i$Goal: $min\frac{1}{2}||w|{|}^2+C\sum _{i=1}^n{\xi }_i,s.t.y_i(w^T{x}_i+b)\ge 1-{\xi }_i,{\xi }_i\ge 0$
Lagrangian: $L(w,b,\alpha ,\xi )=\frac{1}{2}||w|{|}^2+C\sum _{i=1}^n{\xi }_i-\sum _{i=1}^n{\alpha }_i(y_i(w^T{x}_i+b)-1+{\xi }_i)-\sum _{i=1}^n{\mu }_i{\xi }_i,{\alpha }_i,{\mu }_i\ge 0$Partial Derivative: $\frac{\partial L}{\partial w}=w-\sum _{i=1}^n{\alpha }_i{y}_i{x}_i=0,\frac{\partial L}{\partial b}=-\sum _{i=1}^n{\alpha }_i{y}_i=0,\frac{\partial L}{\partial {\xi }_i}=C-{\alpha }_i-{\mu }_i=0$Solution: $||w|{|}^2=\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$Dual Problem: $L=\underset{\alpha }{max}\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$s.t. $\sum _{i=1}^n{\alpha }_i{y}_i=0,0\le {\alpha }_i\le C$
Weight vector: $w^{\ast }=\sum _{i=1}^n{\alpha }_i{y}_i{x}_i$Bias: $b^{\ast }=y_k-\sum _{i=1}^n{\alpha }_i{y}_i{x}_i^T{x}_k\text{for any }0<{\alpha }_k<C$The reason that ξ disappears: The slack variables ${\xi }_i$ disappear in the dual problem because they are implicitly handled through the Lagrange multipliers ${\alpha }_i$. By taking the derivative of the Lagrangian with respect to ${\xi }_i$, we obtain:$\frac{\partial L}{\partial {\xi }_i}=C-{\alpha }_i-{\mu }_i=0$ This relationship ensures that ${\alpha }_i$ is bounded by $0\le {\alpha }_i\le C$. Consequently, the slack variables ${\alpha }_i$ do not explicitly appear in the dual formulation. Instead, the dual problem balances maximizing the margin and allowing for misclassification through the constraint on ${\alpha }_i$.

Kernel SVMHyperplane: $H=\{w|w^T\varphi (x)+b=0\}$Constraint: $y_i(w^T\varphi (x_i)+b)\ge 1-{\xi }_i,{\xi }_i\ge 0,\mathrm{\forall }i$Goal: $min\frac{1}{2}||w|{|}^2+C\sum _{i=1}^n{\xi }_i,s.t.y_i(w^T\varphi (x_i)+b)\ge 1-{\xi }_i$Lagrangian (Dual): $L(\alpha )=\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j)$s.t. $\sum _{i=1}^n{\alpha }_i{y}_i=0,0\le {\alpha }_i\le C,\mathrm{\forall }i$Weight vector: $w=\sum _{i=1}^n{\alpha }_i{y}_i\varphi (x_i)$Decision Function: $f(x)=\text{sign}(\sum _{i=1}^n{\alpha }_i{y}_{i}K(x_i,x)+b)$Bias: $b=y_k-\sum _{i=1}^n{\alpha }_i{y}_{i}K(x_i,x_k)\mathrm{\forall }supvec0<{\alpha }_k<C$Kernel Functions:
Linear: $K(x_i,x_j)=x_i^T{x}_j$
Polynomial: $K(x_i,x_j)=(x_i^T{x}_j+c{)}^d$
Gaussian (RBF): $K(x_i,x_j)=\exp (-\frac{||x_i-x_j|{|}^2}{2{\sigma }^2})$
Sigmoid: $K(x_i,x_j)=\tanh (\kappa x_i^T{x}_j+c)$

MLE and MAP

MLE

构建似然函数：联合分布 $L(\theta )=\prod _{i=1}^{n}P(X_i|\theta )$。 取对数简化计算：$\ln L(\theta )=\sum _{i=1}^n\ln P(X_i|\theta )$。 求导并设为 0：$\frac{d}{d\theta }\ln L(\theta )=0$，解得 ${\hat{\theta }}_{MLE}$。 验证极值：通过二阶导数等方式确保是最大值。

MAP

结合先验构建后验概率：$P(\theta |X)\propto P(X|\theta )P(\theta )$。 取对数后验函数：$\ln P(\theta |X)\propto \ln P(X|\theta )+\ln P(\theta )$。 求导并设为 0：$\frac{d}{d\theta }\ln P(\theta |X)=0$，解得 ${\hat{\theta }}_{MAP}$。 验证极值：确保找到最大值。